package my.jwds.p590;

import my.jwds.p589.Node;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Postorder {

    public static void main(String[] args) {

        Postorder obj = new Postorder();
        long start = System.currentTimeMillis();
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    public List<Integer> postorder(Node root) {
        if (root == null)return new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        Deque<CountNode> stack = new LinkedList<>();
        stack.push(new CountNode(root));
        while(!stack.isEmpty()){
            while (!stack.peek().isFinish()) {
                stack.push(stack.peek().getChild());
            }
            res.add(stack.pop().node.val);
        }
        return res;
    }



    class CountNode{
        Node node;
        int count;

        public CountNode(Node node) {
            this.node = node;
            this.count = 0;
        }
        public boolean isFinish(){
            return node.children == null || node.children.size() == count;
        }

        public CountNode getChild(){
            return new CountNode(node.children.get(count++));
        }
    }

}